package day10;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
 *
 *
 *
 * 示例：
 *
 * 输入：S = "ababcbacadefegdehijhklij"
 * 输出：[9,7,8]
 * 解释：
 * 划分结果为 "ababcbaca", "defegde", "hijhklij"。
 * 每个字母最多出现在一个片段中。
 * 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
 */
public class Solution1 {
    public List<Integer> partitionLabels(String s) {
        Map<Character,Integer> rightMap = new HashMap<>();
        int len = s.length();
        for(int i = len-1;i>=0;i--){
            if(!rightMap.containsKey(s.charAt(i))){
                rightMap.put(s.charAt(i),i);
            }
        }
        int left = 0;
        List<Integer> list = new ArrayList<>();
        while(left<len){
            char chr = s.charAt(left);
            int right = rightMap.get(chr);
            int index = left;
            while(index<right){
                if(rightMap.get(s.charAt(index))<=right){
                    index++;
                }else{
                    right = rightMap.get(s.charAt(index));
                }
            }
            list.add(right-left+1);
            left = right+1;
        }
        return list;
    }
}
